package org.hot100.h031;

import java.util.Arrays;

/**
 * @Author: wjy
 * @Date: 2021/12/10 14:54
 */
public class Solution {

    public static void main(String[] args) {

        int[] ints = {1,4,2,5};

        Solution solution = new Solution();
        solution.nextPermutation4(ints);
        System.out.println(Arrays.toString(ints));

    }

/*    public void nextPermutation(int[] nums) {
        int len = nums.length, temp = 0;
        for (int i = len - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                Arrays.sort(nums, i, len);
                for (int j = i; j < len; j++) {
                    if (nums[j] > nums[i - 1]) {
                        temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        return;
                    }
                }
            }
        }
        Arrays.sort(nums);
    }*/

    public void nextPermutation(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return;
        }
        
        int len = nums.length, temp = 0;

        // 以 12385764 为例
        for (int i = len - 1; i > 0; i--) {

            // 从数组后面向前寻找数组的第一个升序序列，找到第一个升序区间的倒数第二个数字
            if (nums[i] > nums[i - 1]) {

                // 升序序列的最后一个节点为起点，一直到数组最后一个节点，将这个范围内的数组变为升序序列。如：7， 6， 4 -> 4, 6, 7
                Arrays.sort(nums, i, len);
                for (int j = i; j < len; j++) {

                    // 将排序后的数组与 5 比较，找到第一个比 5 大的数字，交换
                    if (nums[i - 1] < nums[j]) {
                        temp = nums[i - 1];
                        nums[i - 1] = nums[j];
                        nums[j] = temp;
                        return;
                    }
                }
            }
        }

        // 如果数组中不存在任何一个前一位比后一位小的情况，证明整个数组是倒序排列的，直接将其排序即可
        Arrays.sort(nums);
    }

    public void nextPermutation2(int[] nums) {

        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {

                Arrays.sort(nums, i, nums.length);

                for (int j = i; j < nums.length; j++) {
                    int temp = 0;
                    if (nums[j] > nums[i - 1]) {
                        temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        return;
                    }
                }
            }
        }

        Arrays.sort(nums);
    }

    public void nextPermutation3(int[] nums) {
        for (int i = nums.length - 1; i > 0; i++) {
            if (nums[i - 1] < nums[i]) {
                Arrays.sort(nums, i, nums.length);
                for (int j = i; j < nums.length; j++) {
                    if (nums[i - 1] < nums[i]) {
                        int temp = nums[i - 1];
                        nums[i - 1] = nums[i];
                        nums[i] = temp;
                        return;
                    }
                }
            }
        }
        Arrays.sort(nums);
    }

    public void nextPermutation4(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                Arrays.sort(nums, i, nums.length);
                for (int j = i; j < nums.length; j++) {
                    if (nums[j] > nums[i - 1]) {
                        int temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        return;
                    }
                }
            }
        }
        Arrays.sort(nums);
    }
}
